package A_review.review7_19;

import slidingWindowAlgorithm.Class76_1;

import java.util.HashMap;

public class HuaDong {
//    最小覆盖子串  就是说要在S(source) 中找到包含T(target) 中全部字母的一个子串，
//    这个子串一定是所有可能子串中最短的。
    public String minWindow(String s, String t) {
        HashMap<Character, Integer> need = new HashMap<>();
        for (char c: t.toCharArray()
             ) {
            need.put(c,need.getOrDefault(c,0)+1);
        }
        int left = 0,right=0;
        int start=0;
        int valid=0;
        char[] schars = s.toCharArray();
        int size = schars.length;
        int minLen=size+1;

        HashMap<Character, Integer> window = new HashMap<>();

        while (right<size){
            char c = schars[right];
            right++;
            //TODO:2023/7/19 第一步使得滑动窗口中包含全部t中的字符
            if (need.containsKey(c)){
                window.put(c,window.getOrDefault(c,0)+1);
                if (window.get(c).equals(need.get(c))){
                    valid++;
                }
            }
            //TODO:2023/7/19   当window里面全部包含t中所需要的字符的时候  开始优化窗口寻求最优解
            int size1 = need.size();
            //TODO:2023/7/19 这里不太会处理啦  哈哈哈哈哈
            //TODO:2023/7/19  if (valid==size1){ 用while

            while (valid==size1){
                char c1 = schars[left];
                left++;
                if (need.containsKey(c1)){
                    if (window.get(c1).equals(need.get(c1))){
                        valid--;
                    }
                    window.put(c1,window.get(c1)-1);
                }
                if (valid!=size1){
                    if (right-left+1<minLen){
                        start=left-1;
                        minLen=right-left+1;
                    }
                }
            }

        }

        return  minLen == size + 1 ? "" : s.substring(start, start + minLen);
    }


//    字符串排列
  public  boolean checkInclusion(String s1, String s2) {
        boolean res=false;
      HashMap<Character, Integer> need = new HashMap<>();
      for (char c: s1.toCharArray())
      {
          need.put(c,need.getOrDefault(c,0)+1);
      }

      int left = 0,right=0;
      int valid=0;
      char[] schars = s2.toCharArray();
      int size = schars.length;

      HashMap<Character, Integer> window = new HashMap<>();
      while (right<size){
          char c = schars[right];
          right++;
          //TODO:2023/7/19 第一步使得滑动窗口中包含全部t中的字符
          if (need.containsKey(c)){
              window.put(c,window.getOrDefault(c,0)+1);
              if (window.get(c).equals(need.get(c))){
                  valid++;
              }
          }
//          TODO:2023/7/19   当window里面全部包含t中所需要的字符的时候  开始优化窗口寻求最优解
          int size1 = need.size();
          //TODO:2023/7/19 这里不太会处理啦  哈哈哈哈哈
          //TODO:2023/7/19  if (valid==size1){ 用while
          while (valid==size1){
              char c1 = schars[left];
              left++;
              if (need.containsKey(c1)){
                  if (window.get(c1).equals(need.get(c1))){
                      valid--;
                  }
                  window.put(c1,window.get(c1)-1);
              }
              if (valid!=size1){
                  if (right-left+1==s1.length()){
                      res= true;
                      return  res;
                  }
              }
          }
      }
      return  res;
  }










    public static void main(String[] args) {
        HuaDong huaDong = new HuaDong();

//        System.out.println(huaDong.minWindow("ADOBECODEBANC", "ABC"));
        System.out.println(huaDong.checkInclusion("ab", "eidbaooo"));

    }
}
